// rbnode is the basic type for node. 
// For users, use rbtree and new_tree.
typedef struct _rbnode{
    int	            color;
    int	            dir;
    int	            idx;
    double          value;
    double          content;
    struct _rbnode* parent;
    struct _rbnode* child[2];
}* rbnode;

typedef struct _rbtree{
    rbnode root;
    int	   n;
}* rbtree;

extern rbtree new_tree  (double value, double content);

// print_tree(x::rbtree)

#define print_tree(x) _print_tree((x)->root, 0)
extern void _print_tree(rbnode node, int n);

// 'find' returns either found , left or right. 
// left and right means not found, and the direction to the
// closest node is left/right.

#define found -1
#define left   0
#define right  1
extern int find      (rbtree tree, double x, rbnode* ans);

// find the idx'th node
extern rbnode get       (rbtree tree, int idx);

// insert a node to the tree
extern void   insert    (rbtree tree, double value, double content);

// delete a node with following return code
#define node_not_exist (-1)
#define node_deleted (0)
extern int delete    (rbtree tree, double x);
extern int _ntree    (rbnode root);
#define ntree(tree) _ntree((tree)->root)
